package Algorithm.greedyAlgorithm;

/**
 * 45. 跳跃游戏 II https://leetcode.cn/problems/jump-game-ii/description/
 */
public class Jump {

    public static void main(String[] args) {
        new Jump().jump(new int[]{2,3,1,1,4});
    }

    /**
     * 思路：从下标s起跳，每次从能跳到的范围[s+1,k]内选择能跳得最远的下标作为下一个起跳点
     */
    public int jump(int[] nums) {
        if (nums.length <= 1) return 0;
        int count = 0, s = 0, k = nums[s];
        while(k < nums.length-1) {
            int t = k;
            //每次范围[s+1,k]内选择能跳得最远的下标作为下一个起跳点
            for(int i = s+1;i <= t;i++) {
                if(i+nums[i] > k) {
                    k = i+nums[i];
                    s = i;
                }
            }
            count++;
        }
        //最后还要再跳一次到达终点
        return count+1;
    }
}
